package com.study.sort;

import org.junit.jupiter.api.AfterEach;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

import java.util.Arrays;

// 冒泡排序
public class BubbleSort
{
    int[] arr = {5, 4, 6, 1, 3, 2};

    // // 2023新版数据结构与算法
    @Test
    void sort3()
    {
        bubble1(arr, arr.length - 1);
    }

    // 优化 没有发生交换时
    private void bubble1(int[] arr, int right)
    {
        if (right == 0) return;
        int x = 0;  // x 可能的范围是 0 到 right-1
        for (int i = 0; i < right; i++) {
            if (arr[i] > arr[i + 1]) {
                int t = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = t;
                // 发生交换时才改变 x ，如果后面没有再发生交换，则说明后面的元素已经有序
                x = i;
            }
        }
        bubble(arr, x);
    }

    // 递归版
    private void bubble(int[] arr, int right)
    {
        if (right == 0) return;
        for (int i = 0; i < right; i++) {
            if (arr[i] > arr[i + 1]) {
                int t = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = t;
            }
        }
        bubble(arr, right - 1);
    }

    // // 2020版数据结构与算法
    @Test
    void sort2()
    {
        for (int i = arr.length - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if (greater(arr[j], arr[j + 1])) {
                    exch(arr, j, j + 1);
                }
            }
        }
    }

    public static boolean greater(int v, int w)
    {
        return v - w > 0;
    }

    public static void exch(int[] a, int i, int j)
    {
        int temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    // // Java基础 入门到起飞 常见算法
    @Test
    void sort1()
    {
        for (int i = 0; i < arr.length - 1; i++) {  // i 控制冒泡的轮数，i 的值等于右侧已经完成冒泡排序的元素个数
            for (int j = 0;                         // j 表示当前轮冒泡到的索引位置
                 j < arr.length - 1 - i;            // -1 : j+1 ，-i : 减去右侧已经冒泡排序完成的元素个数
                 j++) {
                if (arr[j] > arr[j + 1]) {
                    int t = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = t;
                }
            }
        }
    }

    // 我觉得更易理解的写法
    @Test
    void sort()
    {
        // 冒泡的右边界不断缩小，当右边界缩小到 0 时，只有一个元素了所以不用再比较
        for (int i = arr.length - 1; i > 0; i--) {
            // 从左向右两个相邻的元素两两比较，把最大的移动到当前边界的最右边
            for (int j = 0; j < i; j++) {
                // 当前索引上的元素和相邻的下一个元素比较
                if (arr[j] > arr[j + 1]) {
                    // 如果当前的元素更大则交换
                    int t = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = t;
                }
            }
        }
    }

    // 增加 x 优化右边界
    @Test
    void sort4()
    {
        for (int i = arr.length - 1; i > 0; ) {
            int x = 0;
            for (int j = 0; j < i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int t = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = t;

                    x = j;
                }
            }
            i = x;
        }
    }

    @BeforeEach
    void printArrBefore()
    {
        System.out.println(Arrays.toString(arr));
    }

    @AfterEach
    void printArrAfter()
    {
        System.out.println(Arrays.toString(arr));
    }
}
